package com.mengfou.sortextends;

/**
 * 快排扩展
 * @author mengfou
 */
public class QuickSortExtend {

    /**
     * 一次划分结果，处理两类划分问题，即小于num放置在数组左边，大于num放置在数组右边
     * 即：默认数组中不存在等于num的元素
     * @param arr 待划分数组
     * @param num 划分边界
     */
    public void partitionWithTwoPart(int[] arr, int num){
        int i = -1;
        for (int j = 0; j < arr.length; j++) {
            if(arr[j] > num) continue;
            swap(arr, i + 1, j);
            i++;
        }
    }

    public static void main(String[] args) {

        int[] arr = new int[]{1, 5, 4, 8, 3, 1, 4};
        new QuickSortExtend().partitionWithThreePart(arr, 4);
        for (int i : arr) {
            System.out.print(i+"\t");
        }
        System.out.println();
    }

    /**
     * 划分数组数据为三部分，即小于num放置在数组左边，等于num放置在中间，大于num放置在数组右边
     * @param arr 待划分数组
     * @param num 划分值
     */
    private void partitionWithThreePart(int[] arr, int num) {
        int i = 0, j = arr.length - 1, k = 0;
        while(k <= j){
            if(arr[k] < num) {  // 小于num的情况
                swap(arr, i, k);
                if(i == k) k++;
                i++;
            }else if(arr[k] > num){ // 大于num的情况
                swap(arr, k, j);
                j--;
            } else{   // 等于num的情况
                k++;
            }
        }
    }

    private void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i+"\t");
        }
        System.out.println();
    }

    /**
     * 异或运算进行交换两个数字
     * @param arr 数组
     * @param left 左边下标
     * @param right 右边下标
     */
    private void swap(int[] arr, int left, int right) {
        int temp = arr[left] ^ arr[right];
        arr[left] = temp ^ arr[left];
        arr[right] = arr[left] ^ temp;
    }
}
